﻿using System;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Knapsack
{
    public class RecursiveKnapsackSolver : IKnapsackSolver
    {
        public double Profit(int W, IList<double> values, IList<int> weights)
        {
            int N = values.Count;
            Func<int, int, double> B = null;
            B = (n, c) =>
                    {
                        if (n == 0)
                        {
                            return 0;
                        }
                        if (weights[n - 1] <= c)
                        {
                            return Math.Max(B(n - 1, c), B(n - 1, c - weights[n - 1]) + values[n - 1]);
                        }
                        return B(n - 1, c);
                    };
            return B(N, W);
        }
    }
}
